package code.rocky.leetcode;

import java.util.HashSet;
import java.util.Set;

/**
 * url: https://leetcode.cn/problems/longest-substring-without-repeating-characters/
 */
public class lc3 {

    public static void main(String[] args) {
        String s1 = "abcabcbb";
        String s2 = "bbbbb";
        String s3 = "pwwkew";
        String s4 = "ckilbkd";
        lc3 lc3 = new lc3();
        System.out.println(lc3.lengthOfLongestSubstring2(s1));
        System.out.println(lc3.lengthOfLongestSubstring2(s2));
        System.out.println(lc3.lengthOfLongestSubstring2(s3));
        System.out.println(lc3.lengthOfLongestSubstring2(s4));
    }

    public int lengthOfLongestSubstring(String s) {
        int length = s.length();
        int longestSubstring = 0;
        if (length == 0) return longestSubstring;
        int left = 0, right = 0;
        Set<Character> set = new HashSet<>(length);
        for (int i = 0; i < length; i++) {
            ++right;
            if (!set.add(s.charAt(i))) {
                ++left;
            }
            longestSubstring = Math.max(longestSubstring, (right - left));
        }
        return longestSubstring;
    }

    public int lengthOfLongestSubstring1(String s) {
        int length = s.length();
        int longestSubstring = 0;
        if (length == 0) return longestSubstring;
        int left = 0, right = 0;
        char x = 0;
        Set<Character> set = new HashSet<>(length);
        for (int i = 0; i < length; i++) {
            ++right;
            char e = s.charAt(i);
            if (!set.add(e)) {
                left = (x == e) ? i : ++left;
            }
            x = e;
            longestSubstring = Math.max(longestSubstring, (right - left));
        }
        return longestSubstring;
    }

    public int lengthOfLongestSubstring2(String s) {
        int longestSubstring = 0;
        int length = s.length();
        if (length == 0) return longestSubstring;
        // 哈希集合，记录每个字符是否出现过
        Set<Character> set = new HashSet<Character>();

        // 右指针，初始值为 0，相当于我们在字符串的左边界的左侧，还没有开始移动
        int right = 0;
        for (int i = 0; i < length; ++i) {
            if (i != 0) {
                // 左指针向右移动一格，移除一个字符
                set.remove(s.charAt(i - 1));
            }
            while (right  < length && set.add(s.charAt(right))) {
                // 不断地移动右指针
                ++right;
            }
            // 第 i 到 right 个字符是一个极长的无重复字符子串
            longestSubstring = Math.max(longestSubstring, right - i);
        }
        return longestSubstring;
    }

    public int lengthOfLongestSubstring3(String s) {
        boolean[] flag = new boolean[128];
        int ret = 0;
        int right = 0;
        int length = s.length();
        for (int left = 0; left < length;left++) {
            while (right < s.length() && !flag[s.charAt(right)]) {
                flag[s.charAt(right)] = true;
                right++;
            }
            ret = Math.max(ret, right - left);
            flag[s.charAt(left)] = false;
        }
        return ret;
    }
}
